package leetcode.other.p143;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur =  head;
        ListNode nxt = null;
        while(cur != null){
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

    public void reorderList(ListNode head) {
        // 1->2->3->4->5->null
        // head = 1, mid = 3
        // head2 = reverseList(mid)
        // 1->2->3<-4<-5
        // null<-3
        // head = 1, head2 = 5
        // nxt = head.next = 2
        // nxt2 = head2.next = 4
        // head.next = head2 = 5    1->5
        // head2.next = nxt = 2     5->2
        // head = nxt = 2
        // head2 = nx2 = 4
        // 1->5->2->3<-4
        // nxt = head.next = 3
        // nxt2 = head2.next = null
        // head.next = head2 = 4    2->4
        // head2.next = nxt = 3     4->3
        // head = nxt = 3
        // head2 = nx2 = null
        // 1->5->2->4->3->null
        ListNode mid = middleNode(head);
        ListNode head2 = reverseList(mid);
        while (head2.next != null) {
            ListNode nxt = head.next;
            ListNode nxt2 = head2.next;
            head2.next = head.next;
            head.next = head2;
            head = nxt;
            head2 = nxt2;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        // printList(head);
        Solution s = new Solution();
        // System.out.println("middle node is " + s.middleNode(head).val);
        // head2 = s.reverseList(head2);
        // printList(head2);
        // s.reorderList(head2);
        // printList(head2);
        // System.out.println("middle node is " + s.middleNode(head2).val);
        s.reorderList(head);
        printList(head);
        ListNode head2 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
        // printList(head2);
        // System.out.println("middle node is " + s.middleNode(head2).val);
        s.reorderList(head2);
        printList(head2);
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + "->");
            head = head.next;
        }
        System.out.println("null");
    }
}